﻿// 单链表.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 定于链表节点类型
struct Node
{
    int data;   // 数据域
    Node* next; // 地址域
};

// 链表类型
struct Link
{
    Node* head; // 指向链表的头节点
};

// 链表的初始化
void Init(Link* link)
{
    link->head = (Node*)malloc(sizeof(Node));
    link->head->next = NULL;
}
// 链式的释放
void Destory(Link* link)
{
    while (link->head != NULL)
    {
        Node* p = link->head->next;
        free(link->head);
        link->head = p;
    }
}
// 单链表尾插法
void InsertTail(Link* link, int val)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = val;
    node->next = NULL;

    // 找尾节点
    Node* p = link->head;
    while (p->next != NULL)
    {
        // p从当前节点指向下一个节点
        p = p->next;
    }

    // p就指向了尾节点
    p->next = node;
}
// 单链表的头插法
void InsertHead(Link* link, int val)
{
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;

    n->next = link->head->next;
    link->head->next = n;
}

void Remove(Link* link, int val)
{
    Node* pre = link->head;
    Node* p = link->head->next;

    while (p != NULL && p->data != val)
    {
        pre = p;
        p = p->next;
    }

    // p == NULL
    if (p != NULL)
    {
        pre->next = p->next;
        free(p);
    }
}
// 删除指定值的元素
void RemoveAll(Link* link, int val)
{
    Node* pre = link->head;
    Node* p = link->head->next;

    while (p != NULL)
    {
        if (p->data != val)
        {
            pre = p;
            p = p->next;
        }
        else
        {
            pre->next = p->next;
            free(p);
            p = pre->next;
        }
    }
}
// 删除所有指定值的元素

void ShowLink(Link* link)
{
    Node* p = link->head->next; // p指向第一个节点
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
// 打印单链表元素的值

Node* ReverseKNode(Link* link, int k)
{
    Node* p1 = link->head->next;
    Node* p2 = link->head->next;

    while (--k > 0)
    {
        if (p2 == NULL)
        {
            return NULL;
        }
        p2 = p2->next;   // data&next
    }

    // p1指向了第一个节点   p2指向了正数第k个节点
    while (p2->next != NULL)
    {
        p2 = p2->next;
        p1 = p1->next;
    }

    return p1;

    // 遍历链表，计算节点的总个数
    //int count = 0;
    //Node* p = link->head->next;
    //while (p != NULL)
    //{
    //    count++;
    //    p = p->next;
    //}

    //// 节点总个数 - k + 1  正数的第几个节点
    //int pos = count - k + 1;
    //if (pos <= 0)
    //{
    //    return NULL;
    //}

    //// 从第一个节点遍历到正数的第几个节点，返回
    //p = link->head->next;
    //while (--pos > 0)  // for (int i=0; i<pos; i++)
    //{
    //    p = p->next;
    //}
    //return p;
}
// 求倒数第K个节点的值   把倒数第k个节点的地址返回，没有返回NULL

Link* MergeLinks(Link* link1, Link* link2)
{
    Node* l = link1->head;
    Node* p1 = link1->head->next;
    Node* p2 = link2->head->next;

    while (p1 != NULL && p2 != NULL)
    {
        if (p1->data >= p2->data)
        {
            l->next = p2;
            l = p2;
            p2 = p2->next;

        }
        else if (p1->data < p2->data)
        {
            l->next = p1;
            l = p1;
            p1 = p1->next;
        }

    }
    if (p1 == NULL)
    {
        l->next = p2;
    }
    if (p2 == NULL)
    {
        l->next = p1;
    }
    return link1;
}
//将两个有序的单链表合并成一个有序的单链表
void Reverselink(Link* link)
{
    Node* p = link->head->next;
    if (p == NULL)
    {
        return;
    }
    p = p->next;
    link->head->next->next = NULL;
    while (p != NULL)
    {
        Node* q = p->next;
        p->next = link->head->next;
        link->head->next = p;
        p = q;
    }
    //逆序一个单链表可以用于从大到小的数字从小到大排列；
    //单链表逆序采用头插法
}
//逆序一个单链表
bool FindLinkCircle(Link* link, int* val)
{
    Node* p = link->head->next;
    Node* q = link->head->next;
    if (q == NULL)
    {
        return false;
    }
    //定义两个指针开始都指向头结点
    //未知单链表指针每走一步都要判空
    //一个指针每次走两个节点；
    //一个指针每次走一个节点；
    //当两个指针的地址再次相等时，返回有环：0，否则返回无环:1。
    while (p != NULL && q != NULL)
    {
        p = p->next->next;
        q = q->next;
        if (q == p)
        {
            Node* z;
            Node* k;

            z = link->head->next;
            k = p;
            while (k != z)
            {
                z = z->next;
                k = k->next;
            }
            *val = z->data;

            return true;
        }
    }
    return false;

}
//快慢指针解决单链表是否存在环以及环的入口节点
bool LinkCross(Link* link1, Link* link2, int *val)
{
    Node* p1 = link1->head->next;
    Node* p2 = link2->head->next;
    int num1 = 0;
    int num2 = 0;
    int m = 0;
    while (p1 != NULL)
    {
        p1 = p1->next;
        ++num1;
    }
    while (p2 != NULL)
    {
        p2 = p2->next;
        ++num2;
    }
    p1 = link1->head->next;
    p2 = link2->head->next;

    if (num1 > num2)//计算链表1和链表2的长度，比较其长短
    {
        m = num1 - num2;
        while (m > 0)
        {
            p1 = p1->next;
            m--;
        }
    }
    else
    {
        m = num2 - num1;
        while (m > 0)
        {
            p2 = p2->next;
            m--;
        }
    }
    while (p1 != p2)
    {
        p1 = p1->next;
        p2 = p2->next;
        if (p1 == NULL || p2 == NULL)
        {
            return false;
        }
    }
    *val = p1->data;
    return true;

}
//求两个单链表是否相交
int main()
{

    Node head1 = { 0, NULL };
    Node head2 = { 0, NULL };
    Node n1 = { 23, NULL };
    Node n2 = { 78, NULL };
    Node n3 = { 31, NULL };
    Node n4 = { 90, NULL };
    Node n5 = { 72, NULL };
    Node n6 = { 60, NULL };
    Node n7 = { 61, NULL };
    Node n8 = { 38, NULL };
    head1.next = &n1;
    n1.next = &n2;
    head2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = &n6;
    n2.next = &n6;
    n6.next = &n7;
    n7.next = &n8;
    Link link1 = { &head1 };
    Link link2 = { &head2 };
    int val;
    printf("%d \n", LinkCross(&link1, &link2, &val));
    printf("%d\n", val);

}
#if 0
int main()
{
    Node head1 = { 0, NULL };
    Node n1 = { 23, NULL };
    Node n2 = { 78, NULL };
    Node n3 = { 31, NULL };
    Node n4 = { 90, NULL };
    Node n5 = { 72, NULL };
    Node n6 = { 60, NULL };
    Node n7 = { 61, NULL };
    Node n8 = { 38, NULL };

    head1.next = &n1;
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = &n6;
    n6.next = &n7;
    n7.next = &n8;
    //n8.next = &n4;
    int val;
    Link link = { &head1 };//定义一个链表并初始化；
    printf("%d \n", FindLinkCircle(&link, &val));
    if (FindLinkCircle(&link, &val) == true)//如果链表成环，打印成环时的节点的值
    {
        printf("%d\n", val);
    }
}
//验证快慢指针解决单链表是否存在环以及环的入口节点
#endif
#if 0
int main()
{
    Link link1;
    Link link2;
    Init(&link1);
    Init(&link2);
    //srand(time(0));
    //// 随机20个100内的整数，尾插
    //for (int i = 0; i < 20; i++)
    //{
    //    InsertTail(&link, rand() % 100);
    //}

    //// 打印链表数据
    //ShowLink(&link);

    //// 随机20个100内的整数，尾插
    //for (int i = 0; i < 20; i++)
    //{
    //    InsertHead(&link, rand() % 100);
    //}

    InsertTail(&link1, 20);
    InsertTail(&link1, 32);
    InsertTail(&link1, 50);
    InsertTail(&link2, 21);
    InsertTail(&link2, 72);
    InsertTail(&link2, 89);
    InsertTail(&link2, 95);
    // 打印链表数据
    ShowLink(&link1);
    ShowLink(&link2);
    Link* link3 = MergeLinks(&link1, &link2);
    ShowLink(link3);//链表合并
    Reverselink(link3);//链表倒序
    ShowLink(link3);
    //ShowLink(link3);
    //Remove(&link, 21);
    //// 打印链表数据
    //ShowLink(&link);

    //RemoveAll(&link, 20);
    //// 打印链表数据
    //ShowLink(&link);
}
#endif